package com.example.demo.util;

/**
 * @author : shenxiang
 * @date : 2022/10/23 13:58
 * @description : 分治法
 */
public class ExampleMerge {

    public static void main(String[] args) {
        int[] arr = {5,2,6,87,6,2,1,3,8,99,2,22,11,56,88};
        MergeSort(arr,0,arr.length-1);
        for (int i : arr) {
            System.out.println(i);
        }
    }


    private static void MergeSort(int[] arr,int p,int r){
        int q;
        if (p < r){
            q = (p+r) / 2;
            MergeSort(arr,p,q);
            MergeSort(arr,q+1,r);
            Merge(arr,p,q,r);
        }
    }

    private static void Merge(int[] arr,int p,int q,int r){
        int n1 = q - p + 1,n2 = r-q ;
        int[] L = new int[50];
        int[] R = new int[50];

        for (int i = 0; i < n1; i++) {
            L[i] = arr[p+i];
        }
        for (int i = 0; i < n2; i++) {
            R[i] = arr[q+i+1];
        }
        L[n1] = Integer.MAX_VALUE;
        R[n2] = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        for (int k = p; k < r + 1; k++) {
            if (L[i] < R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
        }
    }
}
